# nSum

def two_sum(nums: list, start, target):
    lo = start
    hi = len(nums) - 1
    rs = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        left = nums[lo]
        right = nums[hi]
        if s == target:
            rs.append([nums[lo], nums[hi]])
            while lo < hi and nums[lo] == left:
                lo += 1
            while lo < hi and nums[hi] == right:
                hi -= 1
        elif s > target:  # 最大值加上左边的都大于target所以左移右指针
            while lo < hi and nums[hi] == right:
                hi -= 1
        elif s < target:
            while lo < hi and nums[lo] == left:
                lo += 1
    return rs


# n：n个数之和
def n_sum(nums, n, start, target):
    res = []
    sz = len(nums)
    # 至少是2Sum，且数组大小不应该小于n
    if n < 2 or sz < n:
        return res
    if n == 2:
        res = two_sum(nums, start, target)
    else:
        # n > 2 时，递归计算 (n-1)Sum 的结果
        temp_index = 0  # 存储临时下标
        for i, v in enumerate(nums):
            if i <= temp_index:
                continue
            t = n_sum(nums, n - 1, i + 1, target - nums[i])
            for j in t:
                j.append(nums[i])
                res.append(j)
            # 跳过第一个数字重复的情况，否则会出现重复结果
            while temp_index < n - 1 and nums[temp_index] == nums[temp_index + 1]:
                temp_index += 1
    return res


a = a = [-1, 0, 1, 2, -1, 4]
print(n_sum(a, 4, 0, 2))
